﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using System.Xml.Serialization;

namespace PPClasses
{
    public abstract class Solver
    {
        public readonly List<Portal> PortalPoints;
        private static DateTime StartTime = DateTime.MinValue;

        /// <summary>
        /// These pairs must be in the final solution
        /// </summary>
        public List<Pair> MustLink;

        /// <summary>
        /// Choose from these intersecting pairs
        /// </summary>
        public List<Pair> PairChoices;

        /// <summary>
        /// Array of blocking pairs for PairChoices
        /// </summary>
        public List<List<int>> ChoicesBlockNumList;

        /// <summary>
        /// Dictionary of blocking pairs for any given pair
        /// </summary>
        public Dictionary<Pair, List<Pair>> ChoicesBlock;

        /// <summary>
        /// All pairs (MustLink + PairChoices)
        /// </summary>
        public List<Pair> AllPairs;

        public static double PercentDone = 0;
        public bool CompletelyDone;

        //public List<Pair> CurrentPairs = new List<Pair>();

        public class ScoreKeeper
        {
            public int Score;
            public int Tris;
            public int Links;
            public String PairsText;
        }

        protected Solver(List<Portal> points)
        {
            PortalPoints = points;
            Precalculate();
        }

        private void Precalculate()
        {
            int npt = PortalPoints.Count;

            AllPairs = new List<Pair>();
            for (int a = 0; a < npt; a++)
            {
                for (int b = a + 1; b < npt; b++)
                {
                    AllPairs.Add(new Pair(a, b));
                }
            }

            // Find all links that are never crossed by any others
            // These are guaranteed to be in the best solution
            MustLink = new List<Pair>();
            PairChoices = new List<Pair>();
            for (int a = 0; a < npt; a++)
            {
                for (int b = a + 1; b < npt; b++)
                {
                    Pair pa = new Pair(a, b);
                    bool bad = false;
                    List<Pair> blockedPairs = new List<Pair>();
                    for (int c = 0; c < npt; c++)
                    {
                        for (int d = c + 1; d < npt; d++)
                        {
                            Pair pb = new Pair(c, d);
                            if (pb.same(pa))
                                continue;

                            if (LinesCross(pa, pb))
                            {
                                bad = true;
                                blockedPairs.Add(pb);
                            }
                        }
                        if (bad) break;
                    }
                    if (!bad)
                    {
                        MustLink.Add(pa);
                        System.Diagnostics.Debug.Print("Must link " + a + "-" + b);
                    }
                    else
                    {
                        PairChoices.Add(pa);
                        System.Diagnostics.Debug.Print("Can link " + a + "-" + b);
                    }
                }
            }

            int pc = PairChoices.Count;
            ChoicesBlockNumList = new List<List<int>>();
            ChoicesBlock = new Dictionary<Pair, List<Pair>>();
            for (int i = 0; i < pc; i++)
            {
                ChoicesBlockNumList.Add(new List<int>());
                ChoicesBlock.Add(PairChoices[i], new List<Pair>());
            }
            for (int a=0;a<pc;a++)
            {
                for (int b = 0; b < pc; b++)
                {
                    if (LinesCross(PairChoices[a], PairChoices[b]))
                    {
                        ChoicesBlockNumList[a].Add(b);
                        ChoicesBlock[PairChoices[a]].Add(PairChoices[b]);
                    }
                }
            }

            int[] lengths = new int[ChoicesBlockNumList.Count];
            for (int i = 0; i < lengths.Length; i++)
                lengths[i] = ChoicesBlockNumList[i].Count;

            StartTime = DateTime.Now;
        }

        protected bool CanAddPair(Pair p, IEnumerable<Pair> pairlist)
        {
            return CanAddPair(PortalPoints, p, pairlist);
        }


        static protected bool CanAddPair(List<Portal> portalPoints, Pair p, IEnumerable<Pair> pairlist)
        {
            // does this pair cross any already existing pairs?
            foreach (Pair p2 in pairlist)
            {
                if (p2.same(p))
                    return false;
                if (LinesCross(portalPoints, p, p2))
                    return false;
            }
            return true;
        }

        public static bool SolutionOK(List<Portal> portalPoints, List<Pair> pairs)
        {
            if (portalPoints == null) 
                return false;
            if (pairs == null) 
                return false;
            List<Pair> ok = new List<Pair>();
            foreach (Pair p in pairs)
            {
                if (!CanAddPair(portalPoints, p, ok))
                    return false;
                ok.Add(p);
            }
            return true;
        }

        protected bool LinesCross(Pair p1, Pair p2)
        {
            return LinesCross(PortalPoints, p1, p2);
        }


        static protected bool LinesCross(List<Portal> portals, Pair p1, Pair p2)
        {
            if (p1.a == p2.a || p1.a == p2.b || p1.b == p2.a || p1.b == p2.b)
                return false; // shared endpoints, can't cross

            Portal p1a = portals[p1.a];
            Portal p1b = portals[p1.b];
            Portal p2a = portals[p2.a];
            Portal p2b = portals[p2.b];

            // See if there is no possible overlap of the lines, 
            // based on the bounds of the points of each

            double p1maxy = Math.Max(p1a.Y, p1b.Y);
            double p2miny = Math.Min(p2a.Y, p2b.Y);
            bool above = p1maxy < p2miny;

            double p1maxx = Math.Max(p1a.X, p1b.X);
            double p2minx = Math.Min(p2a.X, p2b.X);
            bool left = p1maxx < p2minx;

            if (above && left)
                return false;

            double p1miny = Math.Min(p1a.Y, p1b.Y);
            double p2maxy = Math.Max(p2a.Y, p2b.Y);
            bool below = p1miny > p2maxy;

            if (below && left)
                return false;

            double p1minx = Math.Min(p1a.X, p1b.X);
            double p2maxx = Math.Max(p2a.X, p2b.X);

            bool right = p1minx > p2maxx;

            if ((below && right) || (above && right))
                return false;

            Portal r = p1b - p1a;
            Portal s = p2b - p2a;

            // http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
            double rcs = r.cross(s);
            if (Math.Abs(rcs) < 0.000000000001)
                return false; // parallel

            Portal diff = p2a - p1a;

            double t = diff.cross(s) / rcs;
            if (t <= 0 || t >= 1)
                return false;

            double u = diff.cross(r) / rcs;
            return (u > 0 && u < 1);
        }

        protected string DumpPairs(List<Pair> pairs)
        {
            StringBuilder sb = new StringBuilder(4 * pairs.Count);
            foreach (Pair p in pairs)
            {
                sb.Append(p.a.ToString());
                sb.Append("-");
                sb.Append(p.b.ToString());
                sb.Append(" ");
            }
            return sb.ToString();
        }

        protected void EvaluateSolution(List<Pair> pairs)
        {
            this.EvaluateSolution(pairs, false);
        }

        protected void EvaluateSolution(List<Pair> pairs, bool forceToBeBest)
        {
            int numLinks = 0;
            int numTris = 0;

            int npt = PortalPoints.Count;

            bool[,] linked = new bool[npt, npt];

            foreach (Pair p in pairs)
            {
                linked[p.a, p.b] = true;
                linked[p.b, p.a] = true;
                numLinks++;
            }

            for (int a = 0; a < npt; a++)
            {
                for (int b = 0; b < npt; b++)
                {
                    for (int c = 0; c < npt; c++)
                    {
                        if (linked[a, b] && linked[a, c] && linked[b, c])
                        {
                            // ** TODO: test for other points inside this triangle?
                            numTris++;
                        }
                    }
                }
            }
            numTris /= 6;
            int score = numTris * 1250 + numLinks * 313;

            lock (BestScore)
            {
                if (forceToBeBest || score >= BestScore.Score)
                {
                    if (score == BestScore.Score)
                        NumberWithThisScore++;
                    else
                        NumberWithThisScore = 1;
                    BestScore.Score = score;
                    BestPairs = pairs;
                    BestScore.Links = numLinks;
                    BestScore.Tris = numTris;
                    BestScore.PairsText = DumpPairs(pairs);
                    System.Diagnostics.Debug.Print("Score: " + BestScore.Score + " for " + numTris + " fields and " + numLinks + " links : " +
                                                   BestScore.PairsText);
                }
            }
        }

        public ScoreKeeper BestScore = new ScoreKeeper();
        public List<Pair> BestPairs = new List<Pair>();
        public int NumberWithThisScore = 0;
        public bool Stop = false;

        public abstract void GoGoGo();
        virtual public String StatusText()
        {
            String tt = "";
            double mins = DateTime.Now.Subtract(StartTime).TotalMinutes;
            double totalMins = mins / (PercentDone / 100.0);

            if (!CompletelyDone && PercentDone > 0)
            {
                if (totalMins > 120)
                    tt = (mins / 60).ToString("F1") + "/" + (totalMins / 60).ToString("F1") + " hours.";
                else
                    tt = mins.ToString("F1") + "/" + totalMins.ToString("F1") + " minutes.";
            }
            tt = PercentDone.ToString("F1") + "%  " + tt;

            lock (BestScore)
            {
                return tt + " " + BestScore.Links + " links, " + BestScore.Tris + " fields = " + BestScore.Score +
                       " AP.  " +
                       NumberWithThisScore + " with this score.  " + (Stop ? "Stopped.  " : "") +
                       (CompletelyDone ? "Done.  " : "");
            }
        }

        public abstract bool CanThread { get; }

        public static List<Pair> LoadPairsFrom(String filename)
        {
            XmlSerializer deserializer = new XmlSerializer(typeof(List<Pair>));
            List<Pair> dd = null;
            using (TextReader textReader = new StreamReader(filename))
            {
                dd = (List<Pair>)deserializer.Deserialize(textReader);
                textReader.Close();
            }
            return dd;
        }

        public void SavePairsTo(String filename)
        {
            XmlSerializer serializer = new XmlSerializer(typeof(List<Pair>));
            using (TextWriter textWriter = new StreamWriter(filename))
            {
                serializer.Serialize(textWriter, BestPairs);
                textWriter.Close();
            }
        }
    }
}
